Design a HashMap without using any built-in hash table libraries.
To be specific, your design should include these functions:
put(key, value): Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.remove(key): Remove the mapping for the value key if this map contains the mapping for the key.
MyHashMap hashMap = new MyHashMap(); hashMap.put(1, 1); hashMap.put(2, 2); hashMap.get(1); // returns 1 hashMap.get(3); // returns -1 (not found) hashMap.put(2, 1); // update the existing value hashMap.get(2); // returns 1 hashMap.remove(2); // remove the mapping for 2 hashMap.get(2); // returns -1 (not found)
- All keys and values will be in the range of
[0, 1000000]. - The number of operations will be in the range of
[1, 10000]. - Please do not use the built-in HashMap library.
structMyHashMap{buckets:Vec<Vec<(i32,i32)>>,}/** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */implMyHashMap{/** Initialize your data structure here. */fnnew() -> Self{Self{buckets:vec![Vec::new();1000],}}/** value will always be non-negative. */fnput(&mutself,key:i32,value:i32){let id = key asusize % 1000;matchself.buckets[id].iter().position(|&x| x.0 == key){Some(i) => self.buckets[id][i].1 = value,None => self.buckets[id].push((key, value)),};}/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */fnget(&self,key:i32) -> i32{let id = key asusize % 1000;for&(k, v)in&self.buckets[id]{if k == key {return v;}} -1}/** Removes the mapping of the specified value key if this map contains a mapping for the key */fnremove(&mutself,key:i32){let id = key asusize % 1000;matchself.buckets[id].iter().position(|&x| x.0 == key){Some(i) => self.buckets[id].remove(i),None => (0,0),};}}/** * Your MyHashMap object will be instantiated and called as such: * let obj = MyHashMap::new(); * obj.put(key, value); * let ret_2: i32 = obj.get(key); * obj.remove(key); */